package datastructure.heap;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @Description: 最大堆的实现
 * @author: Yang Qiang
 * @create: 2021-12-19 10:50
 */
public class MaxHeap<E extends Comparable<E>> {
    // 底层使用ArrayList储存
    private List<E> data;


    // ================功能方法========================

    /**
     * 将任意数组整理成堆: 堆化Heapify
     * @param arrayList: 需要堆化的数组
     */
    public MaxHeap(List<E> arrayList) {
        /*
          1 将当前数组看成一个完全的二叉树, 然后从最后一个非叶子节点进行下沉Sift Down操作
          2 先不考虑叶子节点, 从非叶子节点22开始进行下沉Sift Down操作, 第一个非节点节点就是最后一个节点的父节点
            这样就能一直循环的比较
         */
        this.data = arrayList;

        // 得到第一个非叶子节点
        int index = parent(arrayList.size() - 1);

        // 一直对每个下标进行循环替换
        for (int i = index; i >= 0 ; i--) {
            siftDown(i);
        }

    }

    /**
     * 替换Replace : 取出堆中的最大元素，并且替换成元素e
     * @param: e : 需要替换的元素
     * @return: 堆中最大的元素
     */
    public E replace(E e){
        E max = findMax();
        data.add(0,e);
        siftDown(0);
        return max;
    }

    /**
     * 取出堆中的最大元素
     * @return: 最大元素的具体值
     */
    public E extractMax(){
        // 得到最大元素值
        E ret = findMax();
        /*
          进行下沉操作Sift Down: 为了维护堆的特征, 父节点比子节点大
         */
        // 1 最大元素和最大元素进行替换:交换根和最后一个叶子节点
        Collections.swap(data,0,data.size()-1);
        // 2 删除交换后的根, 因为我们要把它返回出去的
        data.remove(data.size()-1);
        // 3 进行下沉操作维护特征sift down
        siftDown(0);

        // 维护完毕, 返回最大值
        return ret;
    }

    /**
     * 循环操作: 进行下沉操作维护特征sift down, 维护父节点比子节点大
     * @param index: 需要维护的节点下标值
     */
    private void siftDown(int index) {
        /*
            为什么用这个作为循环条件, 因为堆的特征之一就是是一个完全二叉树, 也就是父节点如果只有一个节点的话,
            那么这节点一定在左边, 所以最后一个节点的下标就是数组的最大下标
         */
        while (leftChild(index) < data.size()){
            // data.get(j+1)右节点值 大于 data.get(j)左节点值, 那么就把交换的下标给右边
            // j就是要和目标下标交换的下标
            int j = leftChild(index);
            if (j + 1 < data.size() && data.get(j+1).compareTo(data.get(j))>0){
                j++;
            }
            // 如果维护的节点大于了左右最大的子节点, 那么就循环结束
            if(data.get(index).compareTo(data.get(j))>=0){
                break;
            }
            // 下标替换, 然后下标赋值, 继续循环比较
            Collections.swap(data,index,j);
            index = j;
        }
    }

    public E findMax() {
        return data.get(0);
    }


    /**
     * 往堆中添加元素
     * @param e
     */
    public void add(E e){
        // 添加到数组最后一个位置
        data.add(e);
        // 最后一个位置元素进行上移操作, 来维护堆的特征: 父节点比子节点大, sift up
        siftUp(data.size()-1);
    }
    /**
     * sift up上移操作
     * @param index: 需要上移操作的节点
     */
    private void siftUp(int index) {
        // 为0就是第一个下标 && 父节点比子节点小就一直交换
        while (index > 0 && data.get(index).compareTo( data.get(parent(index))) >0){
            Collections.swap(data, index, parent(index));
            // 下标赋值, 然后继续循环比较, 不赋值的话就一直在比较固定了两个
            index = parent(index);
        }
    }

    /**
     * 得到一个节点索引值的父节点索引值
     * @param index: 当前节点的索引值
     * @return: 父节点索引值
     */
    public int parent(int index){
        if (index <= 0){
            throw  new RuntimeException("索引值非法");
        }
        return (index - 1) / 2;
    }

    /**
     * 得到一个节点的左子节点的索引值
     * @param index
     * @return
     */
    public int leftChild(int index){
        return  index * 2 + 1;
    }

    /**
     * 得到一个节点的右子节点的索引值
     * @param index
     * @return
     */
    public  int rightChild(int index){
        return index * 2 + 2;
    }

    // ================基础方法========================
    public MaxHeap() {
        data = new ArrayList<>();
    }
    /**
     * 初始化指定大小的集合
     * @param size
     */
    public MaxHeap(int size) {
        data = new ArrayList<>(size);
    }

    /**
     * 返回堆中数组元素的个数
     * @return
     */
    public int size(){
        return data.size();
    }

    /**
     * 判断堆中是否为空
     * @return
     */
    public boolean isEmpty(){
        return data.isEmpty();
    }

    public List<E> getData() {
        return data;
    }

    public void setData(List<E> data) {
        this.data = data;
    }
}
